//第一版 并查集
public class UnionFind1 implements UF {

    private int[] id;

    public UnionFind1(int capacity){
        this.id = new int[capacity];

        for(int i=0;i<id.length;i++){
            id[i] = i;
        }

    }

    @Override
    public int getSize() {
        return id.length;
    }

    private int find(int p){
        if(p<0 || p>=id.length){
            throw new IllegalArgumentException("p is Illegal");
        }
        return id[p];
    }

    //查看元素p和q是否在同一集合
    //O(1)复杂度
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //合并元素p和q所在的集合
    //O(n)时间复杂度
    @Override
    public void unionElements(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if(pID == qID){
            return;
        }
        for(int i=0;i<id.length;i++){
            if(id[i] != qID){
                id[i] = qID;
            }
        }
    }
}
